package org.example.algorithm.dp;

import java.util.Arrays;

public class IsInterleaveSolution {

    public static void main(String[] args) {
        String s1 = "aabcc";
        String s2 = "dbbca";
        String s3 = "aadbbcbcac";
        IsInterleaveSolution solution = new IsInterleaveSolution();
        boolean res = solution.isInterleave2(s1, s2, s3);
        System.out.println(res);
    }
    //dfs+memory
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        }
        //ab cd acbd
        //i代表s1索引，j代表s2索引，i+j+1代表s3索引
        //dfs(i,j) = ((s1.charAt(i) == s3.charAt(i+j+1) && dfs(i-1,j))
        // || ((s2.charAt(j) == s3.charAt(i+j+1) && dfs(i, j-1))
        int[][] mem = new int[len1+1][len2+1];
        for (int i=0;i<=len1;i++) {
            Arrays.fill(mem[i], -1);
        }
        return dfs(s1, s2, s3, len1-1, len2-1, mem);
    }

    private boolean dfs(String s1, String s2, String s3, int i, int j, int[][] mem) {
        //边界条件
        if (i<0 && j<0) {
            return true;
        }
        if (mem[i+1][j+1] != -1) {
            return mem[i+1][j+1] == 1;
        }
        if ((j>=0 && s2.charAt(j) == s3.charAt(i+j+1) && dfs(s1, s2, s3, i, j-1, mem))
                || (i>=0 && s1.charAt(i) == s3.charAt(i+j+1) && dfs(s1, s2, s3, i-1, j, mem))) {
            mem[i+1][j+1] = 1;
            return true;
        }
        mem[i+1][j+1] = 0;
        return false;
    }

    public boolean isInterleave2(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        }
        boolean[][] dp = new boolean[len1+1][len2+1];
        dp[0][0] = true;
        for (int i=0;i<len1;i++) {
            if (s1.charAt(i) == s3.charAt(i) && dp[i][0]) {
                dp[i+1][0] = true;
            }
        }
        for (int j=0;j<len2;j++) {
            if (s2.charAt(j) == s3.charAt(j) && dp[0][j]) {
                dp[0][j+1] = true;
            }
        }
        for (int i=0;i<len1;i++) {
            for (int j=0;j<len2;j++) {
                if ((s1.charAt(i) == s3.charAt(i+j+1) && dp[i][j+1]) ||
                        (s2.charAt(j) == s3.charAt(i+j+1) && dp[i+1][j])) {
                    dp[i+1][j+1] = true;
                }
            }
        }
        return dp[len1][len2];
    }
}
